package quwei;

import java.util.Scanner;
import java.util.Arrays;

/*二分搜索技术*/
public class Test3_2 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入数列中的元素个数n为：(输入-1程序结束)");
        int n=scanner.nextInt();
        while(n!=-1) {
            int[] s=new int[n];
            System.out.println("请依次输入数列中的元素：");
            for(int i=0;i<n;i++)
                s[i]=scanner.nextInt();
            Arrays.sort(s);                                  //对数组排序，二分查找要求数列必须有序                            
            System.out.println("排序后的数组为：");
            for(int i=0;i<n;i++)
                System.out.print(s[i]+" ");
            System.out.println();
            System.out.println("请输入要查找的元素：");
            int x=scanner.nextInt();
            int ans=binarySearch(s,x);                     //在数组s中查找元素x
            if(ans==-1)
                System.out.println("改数列中没有要查找的元素");
            else
                System.out.println("要查找的元素在第"+(ans+1)+"位");

            System.out.println("请输入数列中的元素个数n为：(输入-1程序结束)");
            n=scanner.nextInt();
        }
    }

    /*二分查找*/
    public static int binarySearch(int[] s,int x) {
        int low=0;                                         //low指向数组第一个元素
        int high=s.length-1;                               //high指向数组最后一个元素
        while(low<=high) {                                 //主要low<=high就进入循环
            int middle=(low+high)/2;                       //middle为查找范围的中间值
            if(x==s[middle])                               //x等于查找范围的中间值，算法结束
                return middle;
            else if(x<s[middle])                           //x小于查找范围的中间元素，则从前半部分查找
                high=middle-1;                             //重新设置high
            else                                           //x大于查找范围的中间元素，则从后半部分查找
                low=middle+1;
        }
        return -1;
    }
}
